package day_7_13;

import java.util.ArrayDeque;
import java.util.Deque;

public class Main1 {
    /**
     * 84. 柱状图中最大的矩形
     * https://leetcode.cn/problems/largest-rectangle-in-histogram/description/?envType=study-plan-v2&envId=top-100-liked
     */
    public int largestRectangleArea(int[] heights) {
        // 想要知道 i 位置的最大面积的话，那么需要知道 i 位置 左侧的第一个下降的位置 和 右侧的第一个下降的位置
        // 这样就可以根据这两个位置的区间的长度 和 i位置的高度计算出面积
        // 使用 单调栈进行计算出 left 和 right 对应的每一个位置的值
        int n = heights.length;

        int[] left = new int[n];
        Deque<Integer> deque = new ArrayDeque<>();
        for(int i = 0;i < n;i++) {
            int h = heights[i];
            while(!deque.isEmpty() && h <= heights[deque.peek()]) {
                // 说明当前的位置不是 h 这个高度所对应的第一次减小的位置
                deque.pop();
            }
            // 这个时候 如果不为空的话，那么这个栈顶位置的数据就是 相对于h 位置的第一个减小的位置
            left[i] = deque.isEmpty() ? -1 : deque.peek();
            // 之后将这个 h 位置对应的 下标位置进行存入
            deque.push(i);
        }
        // 这样之后，left 这个数组就是 每一个位置对应的 左侧第一个减小的高度位置
        int[] right = new int[n];
        // 统计 i位置的 右侧第一个减小的高度的位置
        // 将栈中的数据都清空
        deque.clear();
        for(int i = n - 1;i >= 0;i--) {
            int h = heights[i];
            while(!deque.isEmpty() && h <= heights[deque.peek()]) {
                deque.pop();
            }
            right[i] = deque.isEmpty() ? n : deque.peek();
            deque.push(i);
        }

        int ret = 0;
        for(int i = 0;i < n;i++) {
            ret = Math.max(ret,heights[i] * (right[i] - left[i] - 1));
        }
        return ret;
    }
}
